SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Distributed constraint optimization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Distributed constraint optimization</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p><b>Distributed constraint optimization</b> (<b>DCOP</b> or <b>DisCOP</b>) is the <a href="Distributed_computing" title="Distributed computing">distributed</a> analogue to <a href="Constraint_optimization" class="mw-redirect" title="Constraint optimization">constraint optimization</a>. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized.

</p><p>Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents). The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents.

</p><p>Problems defined with this framework can be solved by any of the algorithms that are designed for it.

</p><p>The framework was used under different names in the 1980s. The first known usage with the current name is in 1990.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

<p>The main ingredients of a DCOP problem are <i>agents</i> and <i>variables</i>. Importantly, each variable is owned by an agent; this is what makes the problem distributed. Formally, a DCOP is a <a href="Tuple" title="Tuple">tuple</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }</annotation>

</semantics>

</math></span><img src="./4159233e269f0c6acf7469b9b29c7e101f4507ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.379ex; height:2.843ex;" alt="{\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }" loading="lazy"></span>, where:

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> is the <a href="Set_(mathematics)" title="Set (mathematics)">set</a> of <a href="Intelligent_agent" title="Intelligent agent"><i>agents</i></a>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a_{1},\dots ,a_{|A|}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a_{1},\dots ,a_{|A|}\}}</annotation>

</semantics>

</math></span><img src="./6d96a9d6d99092bdd5da9f5c6242ab056ce4d809.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:13.397ex; height:3.176ex;" alt="{\displaystyle \{a_{1},\dots ,a_{|A|}\}}" loading="lazy"></span>.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math></span><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span> is the set of <i>variables</i>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}</annotation>

</semantics>

</math></span><img src="./546edef8d196d6bd4f2dc4c3305d4abc6ed1839c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:16.439ex; height:3.176ex;" alt="{\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}" loading="lazy"></span>.</li>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathfrak {D}}}</annotation>

</semantics>

</math></span><img src="./46c2461a0bd159fa416eeb2bd7a4ac0fed0262ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.934ex; height:2.176ex;" alt="{\displaystyle {\mathfrak {D}}}" loading="lazy"></span> is the set of <i>variable-domains</i>, <span class="nowrap"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}</annotation>

</semantics>

</math></span><img src="./4273cd5521c0bb250c042d69ac08f1dfbb0a3ec8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:18.829ex; height:3.176ex;" alt="{\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}" loading="lazy"></span>,</span> where each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{j}\in {\mathfrak {D}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{j}\in {\mathfrak {D}}}</annotation>

</semantics>

</math></span><img src="./7f1cde1732ba74bb0eebb41a672c9aa5246bb08b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.608ex; height:2.843ex;" alt="{\displaystyle D_{j}\in {\mathfrak {D}}}" loading="lazy"></span> is a <a href="Finite_set" title="Finite set">finite set</a> containing the possible values of variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math></span><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"></span>.

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{j}\in {\mathfrak {D}}}</annotation>

</semantics>

</math></span><img src="./7f1cde1732ba74bb0eebb41a672c9aa5246bb08b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.608ex; height:2.843ex;" alt="{\displaystyle D_{j}\in {\mathfrak {D}}}" loading="lazy"></span> contains only two values (e.g. 0 or 1), then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math></span><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"></span> is called a <i>binary variable</i>.</li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is the <i>cost function</i>. It is a function<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }">

</mrow>

</munder>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }</annotation>

</semantics>

</math></span></span> that maps every possible partial assignment to a cost. Usually, only few values of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> are non-zero, and it is represented as a list of the tuples that are assigned a non-zero value. Each such tuple is called a <i>constraint</i>. Each constraint <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> in this set is a function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./45799f1e8f8f012ac39774584e81117afaceb026.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.245ex; height:2.509ex;" alt="{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }" loading="lazy"></span> assigning a real value to each possible assignment of the variables. Some special kinds of constraints are:

<ul><li><i>Unary constraints</i> - constraints on a single variable, i.e., <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{C}:D_{j}\to \mathbb {R} }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}:D_{j}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./a71583766463aaa280af9c12c4f5089916f71c91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.684ex; height:2.843ex;" alt="{\displaystyle f_{C}:D_{j}\to \mathbb {R} }" loading="lazy"></span> for some <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}\in V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}\in V}</annotation>

</semantics>

</math></span><img src="./03580507ea69925f02dbfc1666e3a2d3f67bd947.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.665ex; height:2.843ex;" alt="{\displaystyle v_{j}\in V}" loading="lazy"></span>.</li>

<li><i>Binary constraints</i> - constraints on two variables, i.e, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }">

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./d00f28c38472ffb5bb18415583ba7cfca2b2c6a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.021ex; height:2.843ex;" alt="{\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }" loading="lazy"></span> for some <span class="nowrap"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j_{1}},v_{j_{2}}\in V}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j_{1}},v_{j_{2}}\in V}</annotation>

</semantics>

</math></span><img src="./9d61c158e7c25057503d7195ee7f627dd50782e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.4ex; height:2.843ex;" alt="{\displaystyle v_{j_{1}},v_{j_{2}}\in V}" loading="lazy"></span>.</span></li></ul></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is the <i>ownership function</i>. It is a function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha :V\to A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha :V\to A}</annotation>

</semantics>

</math></span><img src="./71a05780fe1825136042dc3dcac73bd6453b1566.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.569ex; height:2.176ex;" alt="{\displaystyle \alpha :V\to A}" loading="lazy"></span> mapping each variable to its associated agent. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha (v_{j})\mapsto a_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha (v_{j})\mapsto a_{i}}</annotation>

</semantics>

</math></span><img src="./0565cf0d42f0646668effb000af85541b9223255.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.978ex; height:3.009ex;" alt="{\displaystyle \alpha (v_{j})\mapsto a_{i}}" loading="lazy"></span> means that variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math></span><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"></span> "belongs" to agent <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math></span><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"></span>. This implies that it is agent <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math></span><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"></span>'s responsibility to assign the value of variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math></span><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"></span>. Note that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math></span><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"></span> is not necessarily an <a href="Injective_function" title="Injective function">injection</a>, i.e., one agent may own more than one variables. It is also not necessarily a <a href="Surjection" class="mw-redirect" title="Surjection">surjection</a>, i.e., some agents may own no variables.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta }</annotation>

</semantics>

</math></span><img src="./e4d701857cf5fbec133eebaf94deadf722537f64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.169ex; height:2.176ex;" alt="{\displaystyle \eta }" loading="lazy"></span> is the <i>objective function</i>. It is an <a href="Operator_(mathematics)" title="Operator (mathematics)">operator</a> that aggregates all of the individual <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> costs for all possible variable assignments. This is usually accomplished through summation:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).}">

</mrow>

</munder>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).}</annotation>

</semantics>

</math></span></span></li></ul>

<p>The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \eta (f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta (f)}</annotation>

</semantics>

</math></span><img src="./3bdae0421d14c2012027b5460e47ff4e39a2db5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.257ex; height:2.843ex;" alt="{\displaystyle \eta (f)}" loading="lazy"></span> for a given assignment of the variables.

</p>

<div class="mw-heading mw-heading3"><h3 id="Assignments">Assignments</h3></div>

<p>A <i>value assignment</i> is a pair <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (v_{j},d_{j})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (v_{j},d_{j})}</annotation>

</semantics>

</math></span><img src="./9da606523c4d926fd65c98d87d42df3d86cd56ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.999ex; height:3.009ex;" alt="{\displaystyle (v_{j},d_{j})}" loading="lazy"></span> where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{j}}</annotation>

</semantics>

</math></span><img src="./3fa3426b07cfa37c76382ddbecfb4c880889657f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.119ex; height:2.843ex;" alt="{\displaystyle d_{j}}" loading="lazy"></span> is an element of the domain <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{j}}</annotation>

</semantics>

</math></span><img src="./41eafa45dbe60f5e03b0281cfef1c2eca6bdc4d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.834ex; height:2.843ex;" alt="{\displaystyle D_{j}}" loading="lazy"></span>.

</p><p>A <i>partial assignment</i> is a set of value-assignments where each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math></span><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"></span> appears at most once. It is also called a <i>context.</i> This can be thought of as a function mapping variables in the DCOP to their current values:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.}</annotation>

</semantics>

</math></span></span>

Note that a context is essentially a partial solution and need not contain values for <i>every</i> variable in the problem; therefore, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t(v_{i})\mapsto \emptyset }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t(v_{i})\mapsto \emptyset }</annotation>

</semantics>

</math></span><img src="./9234b87bb5b5e03ed3a9af93caccb72e135e919a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.353ex; height:2.843ex;" alt="{\displaystyle t(v_{i})\mapsto \emptyset }" loading="lazy"></span> implies that the agent <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha (v_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha (v_{i})}</annotation>

</semantics>

</math></span><img src="./2a619533b4507322ac236c2b6e57eb6bc9a331b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.224ex; height:2.843ex;" alt="{\displaystyle \alpha (v_{i})}" loading="lazy"></span> has not yet assigned a value to variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math></span><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy"></span>. Given this representation, the "<a href="Domain_of_a_function" title="Domain of a function">domain</a>" (that is, the set of input values) of the function <code>f</code> can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context (i.e., the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span> function) as an input to the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> function.

</p><p>A <i>full assignment</i> is an assignment in which each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{j}}</annotation>

</semantics>

</math></span><img src="./73fffa4919c0d6268f6a8d9f38c04dd3296fd0a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.037ex; height:2.343ex;" alt="{\displaystyle v_{j}}" loading="lazy"></span> appears exactly once, that is, all variables are assigned. It is also called a <i>solution</i> to the DCOP.

</p><p>An <i>optimal solution</i> is a full assignment in which the objective function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \eta (f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta (f)}</annotation>

</semantics>

</math></span><img src="./3bdae0421d14c2012027b5460e47ff4e39a2db5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.257ex; height:2.843ex;" alt="{\displaystyle \eta (f)}" loading="lazy"></span> is optimized (i.e., maximized or minimized, depending on the type of problem).

</p>

<div class="mw-heading mw-heading2"><h2 id="Example_problems">Example problems</h2></div>

<p>Various problems from different domains can be presented as DCOPs.

</p>

<div class="mw-heading mw-heading3"><h3 id="Distributed_graph_coloring">Distributed graph coloring</h3></div>

<p>The <a href="Graph_coloring" title="Graph coloring">graph coloring</a> problem is as follows: given a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G=\langle N,E\rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=\langle N,E\rangle }</annotation>

</semantics>

</math></span><img src="./8e1014aae2a6b56ce8db3887888bd6eb9d5c756b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.608ex; height:2.843ex;" alt="{\displaystyle G=\langle N,E\rangle }" loading="lazy"></span> and a set of colors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span>, assign each <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\subset N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\subset N}</annotation>

</semantics>

</math></span><img src="./a05816170a72192e4d9f4f05e716879f9258ab3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.557ex; height:2.176ex;" alt="{\displaystyle n\subset N}" loading="lazy"></span>, a color, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\leq C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\leq C}</annotation>

</semantics>

</math></span><img src="./13c11e48fa0346d453ecf485c22c89078a8f99de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.872ex; height:2.343ex;" alt="{\displaystyle c\leq C}" loading="lazy"></span>, such that the number of adjacent vertices with the same color is minimized.

</p><p>As a DCOP, there is one agent per vertex that is assigned to decide the associated color. Each agent has a single variable whose associated domain is of <a href="Cardinality" title="Cardinality">cardinality</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |C|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |C|}</annotation>

</semantics>

</math></span><img src="./d9f9114ede7c5dd63e8b1cbd051e11d343b233f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.06ex; height:2.843ex;" alt="{\displaystyle |C|}" loading="lazy"></span> (there is one domain value for each possible color). For each vertex <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{i}\leq N}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{i}\leq N}</annotation>

</semantics>

</math></span><img src="./e6dd5899e7ea5025e3255dc3cee30eef4883bea2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.356ex; height:2.509ex;" alt="{\displaystyle n_{i}\leq N}" loading="lazy"></span>, there is a variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\in V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\in V}</annotation>

</semantics>

</math></span><img src="./314467aba70c6bd74cacc52d232baacce36f80ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.555ex; height:2.509ex;" alt="{\displaystyle v_{i}\in V}" loading="lazy"></span> with domain <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{i}=C}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{i}=C}</annotation>

</semantics>

</math></span><img src="./892f04c72dde33402dd6dee07429be50819e2869.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.589ex; height:2.509ex;" alt="{\displaystyle D_{i}=C}" loading="lazy"></span>. For each pair of adjacent vertices <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle n_{i},n_{j}\rangle \in E}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle n_{i},n_{j}\rangle \in E}</annotation>

</semantics>

</math></span><img src="./5aa28c83675f919bcc4b116b5e7531926f514e38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.958ex; height:3.009ex;" alt="{\displaystyle \langle n_{i},n_{j}\rangle \in E}" loading="lazy"></span>, there is a constraint of cost 1 if both of the associated variables are assigned the same color: <span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}</annotation>

</semantics>

</math></span></span> The objective, then, is to minimize <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \eta (f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta (f)}</annotation>

</semantics>

</math></span><img src="./3bdae0421d14c2012027b5460e47ff4e39a2db5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.257ex; height:2.843ex;" alt="{\displaystyle \eta (f)}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Distributed_multiple_knapsack_problem">Distributed multiple knapsack problem</h3></div>

<p>The <i>distributed multiple-</i> variant of the <a href="Knapsack_problem" title="Knapsack problem">knapsack problem</a> is as follows: given a set of items of varying volume and a set of knapsacks of varying capacity, assign each item to a knapsack such that the amount of overflow is minimized. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I}</annotation>

</semantics>

</math></span><img src="./535ea7fc4134a31cbe2251d9d3511374bc41be9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.172ex; height:2.176ex;" alt="{\displaystyle I}" loading="lazy"></span> be the set of items, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math></span><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"></span> be the set of knapsacks, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s:I\to \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s:I\to \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./fb3fdadca84312f93d8b8a72d482c0719e0e3e5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.492ex; height:2.176ex;" alt="{\displaystyle s:I\to \mathbb {N} }" loading="lazy"></span> be a function mapping items to their volume, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c:K\to \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c:K\to \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./255cbbfa5ed9cc41bf080d963461850be9fcbb64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.302ex; height:2.176ex;" alt="{\displaystyle c:K\to \mathbb {N} }" loading="lazy"></span> be a function mapping knapsacks to their capacities.

</p><p>To encode this problem as a DCOP, for each <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in I}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in I}</annotation>

</semantics>

</math></span><img src="./2d740fe587228ce31b71c9628e089d1a9b37c6be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.815ex; height:2.176ex;" alt="{\displaystyle i\in I}" loading="lazy"></span> create one variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\in V}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\in V}</annotation>

</semantics>

</math></span><img src="./314467aba70c6bd74cacc52d232baacce36f80ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.555ex; height:2.509ex;" alt="{\displaystyle v_{i}\in V}" loading="lazy"></span> with associated domain <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{i}=K}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{i}=K}</annotation>

</semantics>

</math></span><img src="./c342d73b72163063d1dbd323d7a26b59927a8448.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.888ex; height:2.509ex;" alt="{\displaystyle D_{i}=K}" loading="lazy"></span>. Then for all possible contexts <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span>:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}}">

</mrow>

</munder>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}}</annotation>

</semantics>

</math></span></span>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(t,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(t,k)}</annotation>

</semantics>

</math></span><img src="./4ea64d20be5e53c6c49e3dabc7a114acaaf0f42d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.943ex; height:2.843ex;" alt="{\displaystyle r(t,k)}" loading="lazy"></span> represents the total weight assigned by context <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span> to knapsack <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}</annotation>

</semantics>

</math></span></span>

</p>

<div class="mw-heading mw-heading3"><h3 id="Distributed_item_allocation_problem">Distributed item allocation problem</h3></div>

<p>The <a href="Fair_item_allocation" title="Fair item allocation">item allocation</a> problem is as follows. There are several items that have to be divided among several agents. Each agent has a different valuation for the items. The goal is to optimize some global goal, such as maximizing the sum of utilities or minimizing the envy. The item allocation problem can be formulated as a DCOP as follows.<sup id="cite_ref-:2_2-0" class="reference"><a href="#cite_note-:2-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>Add a binary variable <i>v<sub>ij</sub></i> for each agent <i>i</i> and item <i>j</i>. The variable value is "1" if the agent gets the item, and "0" otherwise. The variable is owned by agent <i>i</i>.</li>

<li>To express the constraint that each item is given to at most one agent, add binary constraints for each two different variables related to the same item, with an infinite cost if the two variables are simultaneously "1", and a zero cost otherwise.</li>

<li>To express the constraint that all items must be allocated, add an <i>n</i>-ary constraint for each item (where <i>n</i> is the number of agents), with an infinite cost if no variable related to this item is "1".</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Other_applications">Other applications</h3></div>

<p>DCOP was applied to other problems, such as:

</p>

<ul><li>coordinating mobile sensors;</li>

<li>meeting and task scheduling.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<p>DCOP algorithms can be classified in several ways:<sup id="cite_ref-yeoh06_3-0" class="reference"><a href="#cite_note-yeoh06-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><i>Completeness</i> - complete search algorithms finding the optimal solution, vs. <a href="Local_search_(optimization)" title="Local search (optimization)">local search</a> algorithms finding a <a href="Local_optimum" class="mw-redirect" title="Local optimum">local optimum</a>.</li>

<li><i>Search strategy</i> - best-first search or depth-first branch-and-bound search;</li>

<li><i>Synchronization</i> among agents - synchronous or asynchronous;</li>

<li><i>Communication</i> among agents - point-to-point with neighbors in the constraint graph, or broadcast;</li>

<li><i>Communication topology</i> - chain or tree.</li></ul>

<p>ADOPT, for example, uses best-first search, asynchronous synchronization, point-to-point communication between neighboring agents in the constraint graph and a constraint tree as main communication topology.

</p>

<th>Algorithm Name

</th>

<th>Year Introduced

</th>

<th><a href="Computational_complexity_theory" title="Computational complexity theory">Memory Complexity</a>

</th>

<th>Number of Messages

</th>

<th><a href="Correctness_(computer_science)" title="Correctness (computer science)">Correctness (computer science)</a>/<br><a href="Completeness_(logic)" title="Completeness (logic)">Completeness (logic)</a>

</th>

<th>Implementations

</th></tr>

<tr>

<td><b>ABT</b><br>Asynchronous Backtracking

</td>

<td>1992

</td>

<td>

</td>

<td>

</td>

<td><small>Note: static ordering, complete</small>

</td>

<td>

</td></tr>

<tr>

<td><b>AWC</b><br>Asynchronous Weak-Commitment

</td>

<td>1994

</td>

<td>

</td>

<td>

</td>

<td><small>Note: reordering, fast, complete (only with exponential space)</small>

</td>

<td>

</td></tr>

<tr>

<td><b>DBA</b><br>Distributed Breakout Algorithm

</td>

<td>1995

</td>

<td>

</td>

<td>

</td>

<td><small>Note: incomplete but fast</small>

</td>

<td><a rel="nofollow" class="external text" href="http://liawww.epfl.ch/frodo1/">FRODO version 1</a>

</td></tr>

<tr>

<td><b>SyncBB</b><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

<p>Synchronous Branch and Bound

</p>

</td>

<td>1997

</td>

<td>

</td>

<td>

</td>

<td><small>Complete but slow</small>

</td>

<td>

</td></tr>

<tr>

<p>Iterative Distributed Breakout

</p>

</td>

<td>1997

</td>

<td>

</td>

<td>

</td>

<td><small>Note: incomplete but fast</small>

</td>

<td>

</td></tr>

<tr>

<td><b>AAS</b><br>Asynchronous Aggregation Search

</td>

<td>2000

</td>

<td>

</td>

<td>

</td>

<td><small>aggregation of values in ABT</small>

</td>

<td>

</td></tr>

<tr>

<td><b>DFC</b><br>Distributed Forward Chaining

</td>

<td>2000

</td>

<td>

</td>

<td>

</td>

<td><small>Note: low, comparable to ABT</small>

</td>

<td>

</td></tr>

<tr>

<td><b>ABTR</b><br>Asynchronous Backtracking with Reordering

</td>

<td>2001

</td>

<td>

</td>

<td>

</td>

<td><small>Note: reordering in ABT with bounded nogoods</small>

</td>

<td>

</td></tr>

<tr>

<td><b>DMAC</b><br>Maintaining Asynchronously Consistencies

</td>

<td>2001

</td>

<td>

</td>

<td>

</td>

<td><small>Note: the fastest algorithm</small>

</td>

<td>

</td></tr>

<tr>

<td><b>Secure Computation with Semi-Trusted Servers</b>

</td>

<td>2002

</td>

<td>

</td>

<td>

</td>

<td><small>Note: security increases with the number of trustworthy servers</small>

</td>

<td>

</td></tr>

<tr>

<td><b>Secure Multiparty Computation For Solving DisCSPs</b><br>(MPC-DisCSP1-MPC-DisCSP4)

</td>

<td>2003

</td>

<td>

</td>

<td>

</td>

<td><small>Note: secure if 1/2 of the participants are trustworthy</small>

</td>

<td>

</td></tr>

<tr>

<td><b>Adopt</b><br>Asynchronous Backtracking<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</td>

<td>2003

</td>

<td>Polynomial (or any-space<sup id="cite_ref-matsui05efficient_6-0" class="reference"><a href="#cite_note-matsui05efficient-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>)

</td>

<td>Exponential

</td>

<td>Proven

</td>

<td><i>Reference Implementation:</i> <a rel="nofollow" class="external text" href="http://teamcore.usc.edu/dcop/">Adopt</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060916180148/http://teamcore.usc.edu/dcop/">Archived</a> 2006-09-16 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a><br>

<p><a rel="nofollow" class="external text" href="https://archive.today/20080919011453/http://dcopolis.sf.net/">DCOPolis</a> (<a href="GNU_Lesser_General_Public_License" title="GNU Lesser General Public License">GNU LGPL</a>)<br>

<a rel="nofollow" class="external text" href="https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/">FRODO</a> (<a href="GNU_Affero_General_Public_License" title="GNU Affero General Public License">AGPL</a>)

</p>

</td></tr>

<tr>

<td><b>OptAPO</b><br>Asynchronous Partial Overlay<sup id="cite_ref-mailler04solving_7-0" class="reference"><a href="#cite_note-mailler04solving-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</td>

<td>2004

</td>

<td>Polynomial

</td>

<td>Exponential

</td>

<td>Proven, but proof of completeness has been challenged<sup id="cite_ref-dcr07proceedings_8-0" class="reference"><a href="#cite_note-dcr07proceedings-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</td>

<td><i>Reference Implementation:</i> <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20070715063706/http://www.ai.sri.com/~mailler/optapo.html">"OptAPO"</a>. <i><a href="Artificial_Intelligence_Center" title="Artificial Intelligence Center">Artificial Intelligence Center</a></i>. <a href="SRI_International" title="SRI International">SRI International</a>. Archived from <a rel="nofollow" class="external text" href="http://www.ai.sri.com/~mailler/optapo.html">the original</a> on 2007-07-15.</cite><br>

<p><a rel="nofollow" class="external text" href="https://archive.today/20080919011453/http://dcopolis.sf.net/">DCOPolis</a> (<a href="GNU_Lesser_General_Public_License" title="GNU Lesser General Public License">GNU LGPL</a>); In Development

</p>

</td></tr>

<tr>

<td><b>DPOP</b><br>Distributed Pseudotree Optimization Procedure<sup id="cite_ref-petcu04distributed_9-0" class="reference"><a href="#cite_note-petcu04distributed-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</td>

<td>2005

</td>

<td>Exponential

</td>

<td>Linear

</td>

<td>Proven

</td>

<td><i>Reference Implementation:</i> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20070629200035/http://liawww.epfl.ch/frodo/">FRODO</a> (<a href="GNU_Affero_General_Public_License" title="GNU Affero General Public License">AGPL</a>)<br>

<p><a rel="nofollow" class="external text" href="https://archive.today/20080919011453/http://dcopolis.sourceforge.net/">DCOPolis</a> (<a href="GNU_Lesser_General_Public_License" title="GNU Lesser General Public License">GNU LGPL</a>)

</p>

</td></tr>

<tr>

<td><b>NCBB</b><br>No-Commitment Branch and Bound<sup id="cite_ref-chechetka06no_10-0" class="reference"><a href="#cite_note-chechetka06no-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</td>

<td>2006

</td>

<td>Polynomial (or any-space<sup id="cite_ref-chechetka06anyspace_11-0" class="reference"><a href="#cite_note-chechetka06anyspace-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>)

</td>

<td>Exponential

</td>

<td>Proven

</td>

<td><i>Reference Implementation:</i> not publicly released<br>

<p><a rel="nofollow" class="external text" href="https://archive.today/20080919011453/http://dcopolis.sourceforge.net/">DCOPolis</a> (<a href="GNU_Lesser_General_Public_License" title="GNU Lesser General Public License">GNU LGPL</a>)

</p>

</td></tr>

<tr>

<td><b>CFL</b><br>Communication-Free Learning<sup id="cite_ref-cfl_12-0" class="reference"><a href="#cite_note-cfl-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</td>

<td>2013

</td>

<td>Linear

</td>

<td>None <small>Note: no messages are sent, but assumes knowledge about satisfaction of local constraint</small>

</td>

<td>Incomplete

</td>

<td>

</td></tr>

</tbody></table>

<p>Hybrids of these DCOP algorithms also exist. BnB-Adopt,<sup id="cite_ref-yeoh06_3-1" class="reference"><a href="#cite_note-yeoh06-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> for example, changes the search strategy of Adopt from best-first search to depth-first branch-and-bound search.

</p>

<div class="mw-heading mw-heading2"><h2 id="Asymmetric_DCOP">Asymmetric DCOP</h2></div>

<p>An <b>asymmetric DCOP</b> is an extension of DCOP in which the cost of each constraint may be different for different agents. Some example applications are:<sup id="cite_ref-:0_13-0" class="reference"><a href="#cite_note-:0-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><i><a href="Event_scheduling" title="Event scheduling">Event scheduling</a></i>: agents who attend the same event might derive different values from it.</li>

<li><i><a href="Smart_grid" title="Smart grid">Smart grid</a></i>: the increase in price of electricity in loaded hours may be different agents.</li></ul>

<p>One way to represent an ADCOP is to represent the constraints as functions:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}:D_{1}\times \dots \times D_{k}\to \mathbb {R} ^{k}}</annotation>

</semantics>

</math></span></span>

</p><p>Here, for each constraint there is not a single cost but a vector of costs - one for each agent involved in the constraint. The vector of costs is of length <i>k</i> if each variable belongs to a different agent; if two or more variables belong to the same agent, then the vector of costs is shorter - there is a single cost for each involved <i>agent</i>, not for each variable.

</p>

<div class="mw-heading mw-heading3"><h3 id="Approaches_to_solving_an_ADCOP">Approaches to solving an ADCOP</h3></div>

<p>A simple way for solving an ADCOP is to replace each constraint <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}</annotation>

</semantics>

</math></span><img src="./4a69f0ac9f508f8a3a238ff0f6da1cf138003542.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.334ex; height:3.009ex;" alt="{\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}" loading="lazy"></span> with a constraint <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }">

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }</annotation>

</semantics>

</math></span><img src="./fedb2d149d120545f470d51ca96ceb3e424c2c9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.245ex; height:2.843ex;" alt="{\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }" loading="lazy"></span>, which equals the sum of the functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}</annotation>

</semantics>

</math></span><img src="./92143c95a5492bec900fbd149e0aa44d250ea1a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.645ex; height:3.176ex;" alt="{\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}" loading="lazy"></span>. However, this solution requires the agents to reveal their cost functions. Often, this is not desired due to privacy considerations.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup>

</p><p>Another approach is called Private Events as Variables (PEAV).<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> In this approach, each variable owns, in addition to his own variables, also "mirror variables" of all the variables owned by his neighbors in the constraint network. There are additional constraints (with a cost of infinity) that guarantee that the mirror variables equal the original variables. The disadvantage of this method is that the number of variables and constraints is much larger than the original, which leads to a higher run-time.

</p><p>A third approach is to adapt existing algorithms, developed for DCOPs, to the ADCOP framework. This has been done for both complete-search algorithms and local-search algorithms.<sup id="cite_ref-:0_13-1" class="reference"><a href="#cite_note-:0-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Comparison_with_strategic_games">Comparison with strategic games</h3></div>

<p>The structure of an ADCOP problem is similar to the game-theoretic concept of a <a href="Simultaneous_game" title="Simultaneous game">simultaneous game</a>. In both cases, there are agents who control variables (in game theory, the variables are the agents' possible actions or strategies). In both cases, each choice of variables by the different agents result in a different payoff to each agent. However, there is a fundamental difference:<sup id="cite_ref-:0_13-2" class="reference"><a href="#cite_note-:0-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>In a simultaneous game, the agents are selfish - each of them wants to maximize his/her own utility (or minimize his/her own cost). Therefore, the best outcome that can be sought for in such setting is an <a href="Nash_equilibrium" title="Nash equilibrium">equilibrium</a> - a situation in which no agent can unilaterally increase his/her own gain.</li>

<li>In an ADCOP, the agents are considered cooperative: they act according to the protocol even if it decreases their own utility. Therefore, the goal is more challenging: we would like to maximize the sum of utilities (or minimize the sum of costs). A Nash equilibrium roughly corresponds to a <a href="Local_optimum" class="mw-redirect" title="Local optimum">local optimum</a> of this problem, while we are looking for a global optimum.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Partial_cooperation">Partial cooperation</h3></div>

<p>There are some intermediate models in which the agents are <i>partially-cooperative</i>: they are willing to decrease their utility to help the global goal, but only if their own cost is not too high. An example of partially-cooperative agents are employees in a firm. On one hand, each employee wants to maximize their own utility; on the other hand, they also want to contribute to the success of the firm. Therefore, they are willing to help others or do some other time-consuming tasks that help the firm, as long as it is not too burdensome on them. Some models for partially-cooperative agents are:<sup id="cite_ref-:1_18-0" class="reference"><a href="#cite_note-:1-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><i>Guaranteed personal benefit</i>: the agents agree to act for the global good if their own utility is at least as high as in the non-cooperative setting (i.e., the final outcome must be a <a href="Pareto_improvement" class="mw-redirect" title="Pareto improvement">Pareto improvement</a> of the original state).</li>

<li><i>Lambda-cooperation</i>: there is a parameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \in [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \in [0,1]}</annotation>

</semantics>

</math></span><img src="./010c0ee88963a09590dd07393d288edd83786b91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.848ex; height:2.843ex;" alt="{\displaystyle \lambda \in [0,1]}" loading="lazy"></span>. The agents agree to act for the global good if their own utility is at least as high as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-\lambda )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-\lambda )}</annotation>

</semantics>

</math></span><img src="./2b85b50d447ec6ee45d5e9a3959c72e233d34717.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.167ex; height:2.843ex;" alt="{\displaystyle (1-\lambda )}" loading="lazy"></span> times their non-cooperative utility.</li></ul>

<p>Solving such partial-coopreation ADCOPs requires adaptations of ADCOP algorithms.<sup id="cite_ref-:1_18-1" class="reference"><a href="#cite_note-:1-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">Constraint satisfaction problem</a></li>

<li><a href="Distributed_algorithm" title="Distributed algorithm">Distributed algorithm</a></li>

<li><a href="Distributed_algorithmic_mechanism_design" title="Distributed algorithmic mechanism design">Distributed algorithmic mechanism design</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes_and_references">Notes and references</h2></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \times }</annotation>

</semantics>

</math></span><img src="./0ffafff1ad26cbe49045f19a67ce532116a32703.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.019ex; margin-bottom: -0.19ex; width:1.808ex; height:1.509ex;" alt="{\displaystyle \times }" loading="lazy"></span>" or "×" denotes the <a href="Cartesian_product" title="Cartesian product">Cartesian product</a>.</span>

</li>

<li id="cite_note-:2-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-:2_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFNetzerMeiselsZivan2016" class="citation journal cs1">Netzer, Arnon; Meisels, Amnon; Zivan, Roie (2016-03-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/s10458-015-9291-7">"Distributed envy minimization for resource allocation"</a></span>. <i>Autonomous Agents and Multi-Agent Systems</i>. <b>30</b> (2): <span class="nowrap">364–</span>402. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10458-015-9291-7">10.1007/s10458-015-9291-7</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1387-2532">1387-2532</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13834856">13834856</a>.</cite></span>

</li>

<li id="cite_note-yeoh06-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-yeoh06_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-yeoh06_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFYeohFelnerKoenig2008" class="citation cs2">Yeoh, William; Felner, Ariel; Koenig, Sven (2008), <a rel="nofollow" class="external text" href="http://idm-lab.org/bib/abstracts/Koen08d.html">"BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm"</a>, <i>Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems</i>, vol. 2, Ifaamas, pp. <span class="nowrap">591–</span>8, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780981738116</bdi></cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFHirayamaYokoo1997" class="citation book cs1">Hirayama, Katsutoshi; Yokoo, Makoto (1997). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/BFb0017442">"Distributed partial constraint satisfaction problem"</a>. In Smolka, Gert (ed.). <i>Principles and Practice of Constraint Programming-CP97</i>. Lecture Notes in Computer Science. Vol. 1330. Berlin, Heidelberg: Springer. pp. <span class="nowrap">222–</span>236. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0017442">10.1007/BFb0017442</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-69642-1</bdi>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">The originally published version of Adopt was uninformed, see

<cite id="CITEREFModiShenTambeYokoo2003" class="citation cs2">Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20191104183451/http://teamcore.usc.edu/papers/2003/modi-aamas03.pdf">"An asynchronous complete method for distributed constraint optimization"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of the second international joint conference on autonomous agents and multiagent systems</i>, <a href="Association_for_Computing_Machinery" title="Association for Computing Machinery">ACM</a> Press, pp. <span class="nowrap">161–</span>168, archived from <a rel="nofollow" class="external text" href="http://teamcore.usc.edu/papers/2003/modi-aamas03.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2019-11-04<span class="reference-accessdate">, retrieved <span class="nowrap">2009-09-07</span></span></cite>. The original version of Adopt was later extended to be informed, that is, to use estimates of the solution costs to focus its search and run faster, see

<cite id="CITEREFAliKoenigTambe2005" class="citation cs2">Ali, Syed; Koenig, Sven; Tambe, Milind (2005), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100707183003/http://teamcore.usc.edu/papers/2005/aamas-paper.pdf">"Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of the fourth international joint conference on autonomous agents and multiagent systems</i>, <a href="Association_for_Computing_Machinery" title="Association for Computing Machinery">ACM</a> Press, pp. <span class="nowrap">1041–</span>8, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1082473.1082631">10.1145/1082473.1082631</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1595930930</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10882572">10882572</a>, archived from <a rel="nofollow" class="external text" href="http://teamcore.usc.edu/papers/2005/aamas-paper.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2010-07-07<span class="reference-accessdate">, retrieved <span class="nowrap">2009-09-07</span></span></cite>. This extension of Adopt is typically used as reference implementation of Adopt.</span>

</li>

<cite id="CITEREFMatsuiMatsuoIwata2005" class="citation cs2">Matsui, Toshihiro; Matsuo, Hiroshi; Iwata, Akira (February 2005), <a rel="nofollow" class="external text" href="http://www.matlab.nitech.ac.jp/~matsuo/AIA05-1.pdf">"Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of Artificial Intelligence and Applications</i>, pp. <span class="nowrap">727–</span>732, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.408.7230">10.1.1.408.7230</a></span></cite></span>

</li>

<li id="cite_note-mailler04solving-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-mailler04solving_7-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFMaillerLesser2004" class="citation book cs1">Mailler, Roger; Lesser, Victor (2004). <a rel="nofollow" class="external text" href="ftp://mas.cs.umass.edu/pub/mailler/mailler-569.pdf">"Solving Distributed Constraint Optimization Problems Using Cooperative Mediation"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems</i>. <a href="IEEE_Computer_Society" title="IEEE Computer Society">IEEE Computer Society</a>. pp. <span class="nowrap">438–</span>445. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1581138644</bdi>.</cite></span>

</li>

<cite id="CITEREFGrinshpounZazonBinshtokMeisels2007" class="citation cs2">Grinshpoun, Tal; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), <a rel="nofollow" class="external text" href="http://liawww.epfl.ch/Publications/Archive/DCR07Proceedings.pdf">"Termination Problem of the APO Algorithm"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning</i>, pp. <span class="nowrap">117–</span>124</cite></span>

</li>

<cite id="CITEREFPetcuFaltings2005" class="citation cs2">Petcu, Adrian; Faltings, Boi (August 2005), <a rel="nofollow" class="external text" href="http://liawww.epfl.ch/cgi-bin/Pubs/single_entry?bibtex_key=Petcu2005">"DPOP: A Scalable Method for Multiagent Constraint Optimization"</a>, <i>Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, Edinburgh, Scotland, pp. 266-271</i></cite></span>

</li>

<cite id="CITEREFChechetkaSycara2006" class="citation cs2">Chechetka, Anton; Sycara, Katia (May 2006), <a rel="nofollow" class="external text" href="http://www.ri.cmu.edu/pub_files/pub4/chechetka_anton_2006_2/chechetka_anton_2006_2.pdf">"No-Commitment Branch and Bound Search for Distributed Constraint Optimization"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems</i>, pp. <span class="nowrap">1427–</span>9, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1160633.1160900">10.1145/1160633.1160900</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1595933034</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:43918609">43918609</a></cite></span>

</li>

<cite id="CITEREFChechetkaSycara2006" class="citation cs2">Chechetka, Anton; Sycara, Katia (March 2006), <a rel="nofollow" class="external text" href="http://www.ri.cmu.edu/pub_files/pub4/chechetka_anton_2006_1/chechetka_anton_2006_1.pdf">"An Any-space Algorithm for Distributed Constraint Optimization"</a> <span class="cs1-format">(PDF)</span>, <a href="AAAI" class="mw-redirect" title="AAAI"><i>Proceedings of the AAAI Spring Symposium on Distributed Plan and Schedule Management</i></a></cite></span>

</li>

<cite id="CITEREFDuffyLeith2013" class="citation cs2">Duffy, K.R.; Leith, D.J. (August 2013), "Decentralized Constraint Satisfaction", <i>IEEE/ACM Transactions on Networking</i>, <b>21</b> (4): <span class="nowrap">1298–</span>1308, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1103.3240">1103.3240</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTNET.2012.2222923">10.1109/TNET.2012.2222923</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11504393">11504393</a></cite></span>

</li>

<li id="cite_note-:0-13"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_13-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_13-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_13-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFGrinshpounGrubshteinZivanNetzer2013" class="citation journal cs1">Grinshpoun, T.; Grubshtein, A.; Zivan, R.; Netzer, A.; Meisels, A. (2013-07-30). <a rel="nofollow" class="external text" href="https://www.jair.org/index.php/jair/article/view/10828">"Asymmetric Distributed Constraint Optimization Problems"</a>. <i>Journal of Artificial Intelligence Research</i>. <b>47</b>: <span class="nowrap">613–</span>647. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1402.0587">1402.0587</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1613%2Fjair.3945">10.1613/jair.3945</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1076-9757">1076-9757</a>.</cite></span>

</li>

<li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><cite id="CITEREFGreenstadtPearceTambe2006" class="citation journal cs1">Greenstadt, Rachel; Pearce, Jonathan P.; Tambe, Milind (2006-07-16). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/1597538.1597642">"Analysis of privacy loss in distributed constraint optimization"</a>. <i>Proceedings of the 21st National Conference on Artificial Intelligence - Volume 1</i>. AAAI'06. Boston: AAAI Press: <span class="nowrap">647–</span>653. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-57735-281-5</bdi>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite id="CITEREFMaheswaranPearceBowringVarakantham2006" class="citation journal cs1">Maheswaran, Rajiv T.; Pearce, Jonathan P.; Bowring, Emma; Varakantham, Pradeep; Tambe, Milind (2006-07-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/s10458-006-5951-y">"Privacy Loss in Distributed Constraint Reasoning: A Quantitative Framework for Analysis and its Applications"</a></span>. <i>Autonomous Agents and Multi-Agent Systems</i>. <b>13</b> (1): <span class="nowrap">27–</span>60. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10458-006-5951-y">10.1007/s10458-006-5951-y</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1573-7454">1573-7454</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16962945">16962945</a>.</cite></span>

</li>

<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><cite id="CITEREFYokooSuzukiHirayama2002" class="citation book cs1">Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi (2002). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/3-540-46135-3_26">"Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information"</a>. In Van Hentenryck, Pascal (ed.). <i>Principles and Practice of Constraint Programming – CP 2002</i>. Lecture Notes in Computer Science. Vol. 2470. Berlin, Heidelberg: Springer. pp. <span class="nowrap">387–</span>401. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-46135-3_26">10.1007/3-540-46135-3_26</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-46135-7</bdi>.</cite></span>

</li>

<li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><cite id="CITEREFRajiv_T._MaheswaranMilind_TambeEmma_BowringJonathan_P._Pearce2004" class="citation web cs1">Rajiv T. Maheswaran; Milind Tambe; Emma Bowring; Jonathan P. Pearce; Pradeep Varakantham (2004). <a rel="nofollow" class="external text" href="https://www.computer.org/csdl/proceedings-article/aamas/2004/20920310/12OmNvjyxDN">"Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling"</a>. <i>computer.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-04-12</span></span>.</cite></span>

</li>

<li id="cite_note-:1-18"><span class="mw-cite-backlink">^ <a href="#cite_ref-:1_18-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:1_18-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFZivanGrubshteinFriedmanMeisels2012" class="citation journal cs1">Zivan, Roie; Grubshtein, Alon; Friedman, Michal; Meisels, Amnon (2012-06-04). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/2343896.2343956">"Partial cooperation in multi-agent search"</a>. <i>Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3</i>. AAMAS '12. <b>3</b>. Valencia, Spain: International Foundation for Autonomous Agents and Multiagent Systems: <span class="nowrap">1267–</span>1268. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-9817381-3-0</bdi>.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Books_and_surveys">Books and surveys</h2></div>

<ul><li><cite id="CITEREFFiorettoPontelliYeoh2018" class="citation cs2">Fioretto, Ferdinando; Pontelli, Enrico; Yeoh, William (2018), <a rel="nofollow" class="external text" href="http://www.jair.org/papers/paper5565.html">"Distributed Constraint Optimization Problems and Applications: A Survey"</a>, <i><a href="Journal_of_Artificial_Intelligence_Research" title="Journal of Artificial Intelligence Research">Journal of Artificial Intelligence Research</a></i>, <b>61</b>: <span class="nowrap">623–</span>698, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1602.06347">1602.06347</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1613%2Fjair.5565">10.1613/jair.5565</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4503761">4503761</a></cite></li>

<li><cite id="CITEREFFaltings2006" class="citation cs2">Faltings, Boi (2006), <a rel="nofollow" class="external text" href="http://www.elsevier.com/wps/find/bookdescription.cws_home/708863/description">"Distributed Constraint Programming"</a>, in Walsh, Toby (ed.), <i>Handbook of Constraint Programming</i>, <a href="Elsevier" title="Elsevier">Elsevier</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-444-52726-4</bdi></cite> A chapter in an edited book.</li>

<li><cite id="CITEREFMeisels2008" class="citation cs2">Meisels, Amnon (2008), <i>Distributed Search by Constrained Agents</i>, <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-84800-040-7</bdi></cite></li>

<li><cite id="CITEREFShohamLeyton-Brown2009" class="citation cs2">Shoham, Yoav; Leyton-Brown, Kevin (2009), <a rel="nofollow" class="external text" href="http://www.masfoundations.org"><i>Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations</i></a>, New York: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-89943-7</bdi></cite> See Chapters 1 and 2; <a rel="nofollow" class="external text" href="http://www.masfoundations.org/download.html">downloadable free online</a>.</li>

<li><cite id="CITEREFYokoo2001" class="citation cs2">Yokoo, Makoto (2001), <i>Distributed constraint satisfaction: Foundations of cooperation in multi-agent systems</i>, <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-67596-9</bdi></cite></li>

<li><cite id="CITEREFYokoo2000" class="citation cs2">Yokoo, M. Hirayama K. (2000), "Algorithms for distributed constraint satisfaction: A review", <i>Autonomous Agents and Multi-Agent Systems</i>, <b>3</b> (2): <span class="nowrap">185–</span>207, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1010078712316">10.1023/A:1010078712316</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2139298">2139298</a></cite></li></ul>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Optimization:_Algorithms,_methods,_and_heuristics381" style="padding:3px"><table class="nowraplinks hlist mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="3"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Optimization:_Algorithms,_methods,_and_heuristics381" style="font-size:114%;margin:0 4em"><a href="Mathematical_optimization" title="Mathematical optimization">Optimization</a>: <a href="Optimization_algorithm" class="mw-redirect" title="Optimization algorithm">Algorithms</a>, <a href="Iterative_method" title="Iterative method">methods</a>, and <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Unconstrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Unconstrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Function_(mathematics)" title="Function (mathematics)">Functions</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Golden-section_search" title="Golden-section search">Golden-section search</a></li>

<li><a href="Powell's_method" title="Powell's method">Powell's method</a></li>

<li><a href="Line_search" title="Line search">Line search</a></li>

<li><a href="Nelder%E2%80%93Mead_method" title="Nelder–Mead method">Nelder–Mead method</a></li>

<li><a href="Successive_parabolic_interpolation" title="Successive parabolic interpolation">Successive parabolic interpolation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Gradient" title="Gradient">Gradients</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Local_convergence" title="Local convergence">Convergence</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Trust_region" title="Trust region">Trust region</a></li>

<li><a href="Wolfe_conditions" title="Wolfe conditions">Wolfe conditions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quasi-Newton_method" title="Quasi-Newton method">Quasi–Newton</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm" title="Berndt–Hall–Hall–Hausman algorithm">Berndt–Hall–Hall–Hausman</a></li>

<li><a href="Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm" title="Broyden–Fletcher–Goldfarb–Shanno algorithm">Broyden–Fletcher–Goldfarb–Shanno</a> and <a href="Limited-memory_BFGS" title="Limited-memory BFGS">L-BFGS</a></li>

<li><a href="Davidon%E2%80%93Fletcher%E2%80%93Powell_formula" title="Davidon–Fletcher–Powell formula">Davidon–Fletcher–Powell</a></li>

<li><a href="Symmetric_rank-one" title="Symmetric rank-one">Symmetric rank-one (SR1)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterative_method" title="Iterative method">Other methods</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Nonlinear_conjugate_gradient_method" title="Nonlinear conjugate gradient method">Conjugate gradient</a></li>

<li><a href="Gauss%E2%80%93Newton_algorithm" title="Gauss–Newton algorithm">Gauss–Newton</a></li>

<li><a href="Gradient_descent" title="Gradient descent">Gradient</a></li>

<li><a href="Mirror_descent" title="Mirror descent">Mirror</a></li>

<li><a href="Levenberg%E2%80%93Marquardt_algorithm" title="Levenberg–Marquardt algorithm">Levenberg–Marquardt</a></li>

<li><a href="Powell's_dog_leg_method" title="Powell's dog leg method">Powell's dog leg method</a></li>

<li><a href="Truncated_Newton_method" title="Truncated Newton method">Truncated Newton</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Hessian_matrix" title="Hessian matrix">Hessians</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Newton's_method_in_optimization" title="Newton's method in optimization">Newton's method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td><td class="noviewer navbox-image" rowspan="5" style="width:1px;padding:0 0 0 2px"><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Constrained_nonlinear381" style="font-size:114%;margin:0 4em"><a href="Nonlinear_programming" title="Nonlinear programming">Constrained nonlinear</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barrier_function" title="Barrier function">Barrier methods</a></li>

<li><a href="Penalty_method" title="Penalty method">Penalty methods</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Differentiable</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Augmented_Lagrangian_method" title="Augmented Lagrangian method">Augmented Lagrangian methods</a></li>

<li><a href="Sequential_quadratic_programming" title="Sequential quadratic programming">Sequential quadratic programming</a></li>

<li><a href="Successive_linear_programming" title="Successive linear programming">Successive linear programming</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Convex_optimization381" style="font-size:114%;margin:0 4em"><a href="Convex_optimization" title="Convex optimization">Convex optimization</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Convex_minimization" class="mw-redirect" title="Convex minimization">Convex<br> minimization</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cutting-plane_method" title="Cutting-plane method">Cutting-plane method</a></li>

<li><a href="Frank%E2%80%93Wolfe_algorithm" title="Frank–Wolfe algorithm">Reduced gradient (Frank–Wolfe)</a></li>

<li><a href="Subgradient_method" title="Subgradient method">Subgradient method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming" title="Linear programming">Linear</a> and<br><a href="Quadratic_programming" title="Quadratic programming">quadratic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Linear_programming#Interior_point" title="Linear programming">Interior point</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Affine_scaling" title="Affine scaling">Affine scaling</a></li>

<li><a href="Ellipsoid_method" title="Ellipsoid method">Ellipsoid algorithm of Khachiyan</a></li>

<li><a href="Karmarkar's_algorithm" title="Karmarkar's algorithm">Projective algorithm of Karmarkar</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Matroid" title="Matroid">Basis-</a><a href="Exchange_algorithm" class="mw-redirect" title="Exchange algorithm">exchange</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Simplex_algorithm" title="Simplex algorithm">Simplex algorithm of Dantzig</a></li>

<li><a href="Revised_simplex_method" title="Revised simplex method">Revised simplex algorithm</a></li>

<li><a href="Criss-cross_algorithm" title="Criss-cross algorithm">Criss-cross algorithm</a></li>

<li><a href="Lemke's_algorithm" title="Lemke's algorithm">Principal pivoting algorithm of Lemke</a></li>

<li><a href="Active-set_method" title="Active-set method">Active-set method</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Combinatorial381" style="font-size:114%;margin:0 4em"><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Paradigms</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Approximation_algorithm" title="Approximation algorithm">Approximation algorithm</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Integer_programming" title="Integer programming">Integer programming</a>

<ul><li><a href="Branch_and_bound" title="Branch and bound">Branch and bound</a>/<a href="Branch_and_cut" title="Branch and cut">cut</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_algorithm" class="mw-redirect" title="Graph algorithm">Graph<br> algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Minimum_spanning_tree52" scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum<br> spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal</a></li></ul>

</div></td></tr></tbody></table><div>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Shortest_path39" scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Flow_network" title="Flow network">Network flows</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dinic's_algorithm" title="Dinic's algorithm">Dinic</a></li>

<li><a href="Edmonds%E2%80%93Karp_algorithm" title="Edmonds–Karp algorithm">Edmonds–Karp</a></li>

<li><a href="Ford%E2%80%93Fulkerson_algorithm" title="Ford–Fulkerson algorithm">Ford–Fulkerson</a></li>

<li><a href="Push%E2%80%93relabel_maximum_flow_algorithm" title="Push–relabel maximum flow algorithm">Push–relabel maximum flow</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr></tbody></table><div></div></td></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks mw-collapsible mw-collapsed navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Metaheuristics381" style="font-size:114%;margin:0 4em"><a href="Metaheuristic" title="Metaheuristic">Metaheuristics</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Evolutionary_algorithm" title="Evolutionary algorithm">Evolutionary algorithm</a></li>

<li><a href="Hill_climbing" title="Hill climbing">Hill climbing</a></li>

<li><a href="Local_search_(optimization)" title="Local search (optimization)">Local search</a></li>

<li><a href="Parallel_metaheuristic" title="Parallel metaheuristic">Parallel metaheuristics</a></li>

<li><a href="Simulated_annealing" title="Simulated annealing">Simulated annealing</a></li>

<li><a href="Spiral_optimization_algorithm" title="Spiral optimization algorithm">Spiral optimization algorithm</a></li>

<li><a href="Tabu_search" title="Tabu search">Tabu search</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="3"><div>

<ul><li><a href="Comparison_of_optimization_software" title="Comparison of optimization software">Software</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-02" href="https://en.wikipedia.org/wiki/?title=Distributed_constraint_optimization&oldid=1293491949">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>